"""
插入排序：
    概述：
        插入排序是一种简单的排序算法，它的工作原理是将未排序的元素一个一个地插入到已排序的元素中。
        将列表分为两部分：
            1：已排序部分
            2：未排序部分
        前边的是已排序部分，后边的是未排序部分。然后拿着未排序部分的每个元素，插入到已排序部分的合适位置即可。
    推理过程：
        1：将列表分为两部分，已排序部分和未排序部分。
        2：从未排序部分取出一个元素，插入到已排序部分的合适位置。
        3：重复第二步，直到未排序部分为空。
    时间复杂度：
        插入排序的时间复杂度:
            最好情况：O(n)：完全有序，只需要遍历数组（无需移动元素），时间复杂度为O(N)
            最坏情况：O(n^2)：完全逆序，需要遍历数组（需要移动元素），时间复杂度为O(N^2)
            平均情况：O(n^2)
    空间复杂度：
        插入排序的空间复杂度是O(1)。
    稳定性：稳定
"""
# 1: 定义函数，insert_sort(my_list)
def insert_sort(my_list):
    # 1.1: 获取列表的长度
    n = len(my_list)
    # 1.2: 外层循环，开始每轮，每次的比较
    for i in range(1, n):
        # 1.3：内循环，从已排序部分的最后一个元素开始，比较到第一个元素
        """
        range(i, 0, -1) 表示从索引i开始递减到1（不包括0）
        每次循环将当前元素与前一个元素比较
        如果当前元素较小，则交换位置
        直到找到正确的位置或到达已排序部分的开头
        """
        for j in range(i, 0, -1):
            # 1.4:具体的比较过程，如果当前元素比前一个元素小，则交换位置
            if my_list[j] < my_list[j-1]:
                my_list[j], my_list[j-1] = my_list[j-1], my_list[j]
            else:
                # 1.5: 如果当前元素比前一个元素大，则提前结束
                break


if __name__ == '__main__':
    my_list = [5, 4, 1, 2, 3]
    print("排序前：", my_list)
    insert_sort(my_list)
    print("排序后：", my_list)
